#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007
class Solution {
public:
    std::vector<std::vector<bool>> visited;
    std::array<int ,5>move = {-1,0,1,0,-1};
    bool exist(std::vector<std::vector<char>>& board, std::string word) {
        int n = board.size();
        int m = board[0].size();
        visited.resize(n,std::vector<bool>(m,false));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(board[i][j]==word[0])
                {
                    visited[i][j]=true;
                   if ( f(i,j,1,word,board))
                       return true;
                    visited[i][j]=false;
                }
                    
            }
        }
        return false;
    }
    bool f(int i,int j,int len,const std::string& word,std::vector<std::vector<char>>& board)
    {
        if (len == word.size())
            return true;
        int n = visited.size();
        int m = visited[0].size();
        
        for (int k=0;k<4;k++)
        {
            int x = i + move[k];
            int y = j + move[k+1];
            if (x<0||y<0||x>=n||y>=m)
                continue;
            if (visited[x][y])
                continue;
            if (board[x][y]==word[len])
            {
                visited[x][y]=true;
                if (f(x,y,len+1,word,board))
                {
                    return true;
                }
                visited[x][y]=false;
            }
        }
        return false;
    }
};
